//
//  Queue.swift
//  Chapter3LinkedList
//
//  Created by TRS-Mobile on 2021/8/31.
//

import Foundation

protocol Queue {
    associatedtype Element
    @discardableResult
    mutating func enqueue(_ e: Element) -> Bool
    @discardableResult
    mutating func dequeue() -> Element?
    var isEmpty: Bool { get }
    var peek: Element? {get}
}

struct QueueArray<T>: Queue {
    
    private var array: [T] = []
    init() {}
    
    @discardableResult
    mutating func enqueue(_ e: T) -> Bool {
        array.append(e)
        return true
    }
    
    @discardableResult
    mutating func dequeue() -> T? {
        return isEmpty ? .none : array.removeFirst()
    }
    
    var isEmpty: Bool {
        return array.isEmpty
    }
    
    var peek: T? {
        return array.first
    }
    
    typealias Element = T
}

extension QueueArray: CustomStringConvertible {
    var description: String {
        return array.description
    }
}

struct QueueLinkedList<T>: Queue {
    
    typealias Element = T
    private var list = DoublyLinkedList<T>()
    init() { }
    
    @discardableResult
    mutating func enqueue(_ e: T) -> Bool {
        list.append(e)
        return true
    }
    
    @discardableResult
    mutating func dequeue() -> T? {
        guard !list.isEmpty, let element = list.first else { return .none }
        return list.remove(element)
    }
    
    var isEmpty: Bool {
        return list.isEmpty
    }
    
    var peek: T? {
        return list.first?.value
    }
}

extension QueueLinkedList: CustomStringConvertible {
    var description: String {
        return list.description
    }
}

struct QueueRingBuffer<T>: Queue {
    
    typealias Element = T
    
    private var ringBuffer: RingBuffer<T>
    init(count: Int) {
        ringBuffer = RingBuffer(count: count)
    }
    
    @discardableResult
    mutating func enqueue(_ e: T) -> Bool {
        ringBuffer.write(e)
    }
    
    @discardableResult
    mutating func dequeue() -> T? {
        return isEmpty ? .none : ringBuffer.read()
    }
    
    var isEmpty: Bool {
        return ringBuffer.isEmpty
    }
    
    var isFull: Bool {
        return ringBuffer.isFull
    }
    
    
    var peek: T? {
        return ringBuffer.first
    }
}

extension QueueRingBuffer: CustomStringConvertible {
    var description: String {
        return ringBuffer.description
    }
}

struct QueueStack<T>: Queue {
    typealias Element = T
    
    var leftStack: [T] = []
    var rightStack: [T] = []
    init() {}
    
    @discardableResult
    mutating func enqueue(_ e: T) -> Bool {
        rightStack.append(e)
        return true
    }
    
    @discardableResult
    mutating func dequeue() -> T? {
        if leftStack.isEmpty {
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }
        return leftStack.popLast()
    }
    
    var isEmpty: Bool {
        return leftStack.isEmpty && rightStack.isEmpty
    }
    
    var peek: T? {
        return !leftStack.isEmpty ? leftStack.last : rightStack.first
    }
}

extension QueueStack: CustomStringConvertible {
    var description: String {
        let printList = leftStack + rightStack.reversed()
        return printList.description
    }
}
